package com.mjlf.algorithms;

/**
 * @ClassName MaxCommonDivisor
 * @Description 求两个数的最大公约数
 * @Author mjlft
 * @Date 2018/9/4 22:18
 * @Version 1.0
 */
public class MaxCommonDivisor {
    public static void main(String[] args){
        System.out.println(getMaxCommonDivisor(0, 3));
    }

    /**
     * 计算最大公约数
     * 原理：
     * 如果num1 和 num2 中其中有一个为0， 那么另一个必然为 最大公约数
     * 那么采用取余法是最好的办法， 如果两个数取余为0， 再用取余数与余数进行再次求取最大公约数，
     * 最后一定会得到其中用一个数为0，另一个数则为最大公约数
     * num1 % num2 ~~ r
     * 则 x*num2 + r = num1
     * 那么剩下的就是求num2 和 r的最大公约数了
     * 如此循环下去，但是需要利用第一个如果（num1 和 num2 其中一个为0，另一个则为最大公约数）最为循环结束条件
     *
     * 下边使用递归实现
     * @param num1
     * @param num2
     * @return
     */
    public static int getMaxCommonDivisor(int num1, int num2){
        if(num2 == 0){
            return num1;
        }
        return getMaxCommonDivisor(num2, num1 % num2);
    }
}
